Digital signals are used in broadcast technology and in other signal processing applications such as audio and video recording and storage.
FIG. 18 shows an example of the construction of a receiver for digitally-transmitted audio signals according a format known as DAB (Digital Audio Broadcasting). A tuner 92 selects signals of a predetermined broadcasting station from signals received via an antenna 91 and outputs the signals to an A/D converter 93. The A/D converter 93 converts supplied signals from analog to digital form. The data recovered by A/D converter 93 includes both guard interval components and symbol components representing the transmitted data. The guard interval components are separated in the conventional manner, by conventional apparatus (not shown). The symbol components are supplied to a memory 100. The data is supplied to memory 100 in ordered sets. Each ordered set may include a series of digital values representing successive values of the signal provided by A/D converter during successive sampling intervals within a block of time used to transmit one or more symbol components.
A Fast Fourier Transform or "FFT" circuit 94 demodulates data which is transmitted in, for example, OFDM (Orthogonal Frequency Division Multiplexing) by performing an FFT computation in order to convert supplied data on a time axis into data on a frequency axis, and thereby separates a plurality of subcarrier waves.
A deinterleave circuit and error correction circuit 95 performs a deinterleave process on data supplied from the FFT circuit 94 and an error correction process thereon. A part of the signals processed by the deinterleave circuit and error correction circuit 95 are supplied to a decoding circuit 96. The decoding circuit 96 demodulates the supplied signals by DQPSK (Differential Quadrature Phase Shift Keying) and converts the demodulated data into analog audio signals, after which it outputs audio signals of the left and right channels to speakers 97 and 98 respectively, causing them to output sounds corresponding to those signals.
Further, an additional data output circuit 99 separates additional data, such as program contents or traffic information, from the signals supplied from the deinterleave circuit and error correction circuit 95 and outputs the signals. The digital data handling components of the receiver other than FFT circuit 94 operate in synchronism with a relatively low-speed system clock 111, whereas FFT circuit 94 operates in synchronism with a relatively high-speed internal clock 113 (FIG. 19) to perform the computations required for FFT transformation. This arrangement in which an FFT circuit operates in synchronism with a high-speed clock, but the other digital components of the apparatus operate in synchronism with a low-speed clock, is found in other digital signal processing devices as well.
A conventional interface between the FFT circuit and the remainder of the apparatus is depicted in FIG. 19. FFT transformation normally requires reordering of the incoming data or reordering of the final computation results provided as output data. The system of FIG. 19 uses input data reordering. Memory 100, operating in synchronism with the low-speed clock 111, accepts incoming sets of data, rearranges the data in a so-called "reverse-digit" sequence, and then outputs it to FFT circuit 94. A reverse-digit sequence is a particular reordering of the data of an ordered set. Where the order of each item of data in the original ordered set is a number M, the order of that item in the rearranged set is a number M', where M' is obtained by expressing M as a numeral in a base r, and reversing the digits of such numeral.
For example, in a case where a set including eight units of data is processed. (i.e., in a case where an FFT computation starting with 8 points is performed), the sequence position or order (0 to 7) of each of the eight units of data can be expressed in a three-bit binary (r=2). The 3rd (011B) unit of data becomes the 6-th (110B) unit of data in a reverse-digit sequence. In a similar manner, the eight units of data f(0) to f(7) are rearranged in a sequence (reverse-digit sequence) of f(0), f(4), f(2), f(6), f(1), f(5), f(3), and f(7).
FIG. 19 shows an example of the construction of the FFT circuit 94. An input buffer 102, as shown in FIG. 20, stores data f(0), f(4), f(2), f(6), f(1), f(5), f(3), and f(7), as previously rearranged in reverse-digit sequence by memory 100. Then, the input buffer 102 outputs the supplied data in an as-is sequence to a selector 103 in synchronization with high-speed internal clock 113 of the FFT circuit 94. That is, the input buffer 102 makes speed adjustments between the low-speed system clock of the receiving apparatus and the high-speed internal clock of the FFT circuit 94.
Then, the selector 103 stores data from the input buffer 102 in a set of locations in an internal memory 104 of the FFT circuit, depicted as the leftmost part of memory 104 in FIG. 20.
Next, a selector 105 initially outputs the 0-th input data f(0) and the 1st input data f(4) from memory 104 to a butterfly computation unit 106. The butterfly computation unit 106 performs a first-stage butterfly computation on these data and stores the computational results in a memory 104 via the selector 103 as the 0-th first-stage computation result data R1(0) and the 1st first-stage computation result data R1(1). A "butterfly computation" is a well-known procedure utilized in FFT and related algorithms. Each butterfly computation uses first and second digital values as inputs and produces two digital values as outputs. The first input is multiplied by a constant. The product is added to the second input to get one output, and the product is subtracted from the second input to get the other output.
In a similar manner, three additional first-stage butterfly computations are performed (i) on the 2nd input data f(2) and the 3rd input data f(6); (ii) on the 4-th input data f(1) and the input 5-th data f(5), and (iii) on the 6-th input data f(3) and the 7-th input data f(7) to provide 2nd through 7-th first-stage computational results R1(2) through R1(7). These further first-stage computational results are stored at respective locations in memory 104, so that that all of the first stage computational results form an ordered set in the memory.
Next, the selector 105 reads out the 0-th data R1(0) and the 2nd data R1(2) of the memory 104, and outputs them to the butterfly computation unit 106. The butterfly computation unit 106 performs a second-stage butterfly computation using these first stage computational results as inputs, to obtain second-stage computational results the R2(0) and R2(2). These second-stage computational results are stored by selector 103 in memory 104 as the 0-th and 2-nd elements of a new ordered set.
Furthermore, the selector 105 reads out the 1st data R1(1) and 3rd data R1(3) and outputs them to the butterfly computation unit 106. The butterfly computation unit 106 performs a second-stage butterfly computation on each of these data and stores the computational results in the memory 104 via the selector 103 as the 1st data R2(1) and the 3rd data R2(3).
In a similar manner, a butterfly computation is performed on the 4-th data R1(4) and the 6-th data R1(6) in the memory 104, and the computational results are stored as the 4-th data R2(4) and the 6-th data R2(6) in the memory 104. A butterfly computation is performed on each of the 5-th data R1(5) and the 7-th data R1(7) of the memory 104, and the computational results are stored as the 5-th data R2(5) and the 7-th data R2(7) in the memory 104. Thus, all of the second-stage computational results are stored in memory 104 as a new ordered set.
Next, the selector 105 reads out the 0-th second stage computational result data R2(0) and the 4-th second stage computational result data R2(4) from the memory 104, and outputs them to the butterfly computation unit 106. The butterfly computation unit 106 performs a third-stage butterfly computation on these data, and stores these final computational results in the memory 104 via the selector 103 as the 0-th final data F(0) and the 4-th final data F(4).
In a similar manner, a third-stage butterfly computation is performed on the 1st and 5-th second stage computational result data R2(1) and R2(5). The computational results are stored as the 1st and 5-th final computational result data F(1) and F(5) in memory 104. Further, a butterfly computation is performed on the 2nd and 6-th second stage computational results R2(2) and R2(6), and the results are stored as the 2nd and 6-th final computational results F(2) and F(6) in memory 104. A butterfly computation is performed on the 3rd and 7-th second stage computational results R2(3) and R2(7) from memory 104, and the computational results are stored as the 3rd and 7-th final computational results F(3) and F(7) in the memory 104. Thus, the internal memory 104, butterfly computation unit 106 and selector 103 of the FFT circuit cooperate to continually transfer data between the memory and the butterfly computation unit, so as to perform the multiple stages of butterfly computations needed in the FFT algorithm. This process yields an ordered set of final data F(0) to F(7), representing the results of the FFT computations.
Next, the selector 105 outputs the final data F(0) to F(7) stored in the memory 104 to an output buffer 107 in synchronization with high-speed internal clock 113.
Then, the output buffer 107 outputs the FFT-computed data F(0) to F(7) to deinterleave circuit and error correction circuit 95 in synchronization with low-speed system clock 111. That is, the output buffer 107 makes speed adjustments between the high-speed internal clock of the FFT circuit 94 and the low-speed system clock of the receiving apparatus.
The conventional apparatus and methods described above require a separate memory 100 for reordering the incoming data. This adds cost and complexity to the apparatus. Moreover, the reordering memory may limit the speed of operation of the apparatus. In other FFT systems, the input data is not reordered but the output data is reordered. In these systems, the data is transferred from the output buffer to a reordering memory similar to memory 100. These systems suffer from the similar problems.